// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include "windows.h"
//
// typedef int DataType;
//
// typedef struct TreeNode {
//     DataType value;
//     struct TreeNode* left;
//     struct TreeNode* right;
// } TreeNode;
//
// // 队列节点结构
// typedef struct QueueNode {
//     TreeNode* data; // 存储数据
//     struct QueueNode* next; // 指向下一个节点
// } QueueNode;
//
// // 队列结构
// typedef struct {
//     QueueNode* front; // 队头指针
//     QueueNode* rear;  // 队尾指针
// } LinkQueue;
//
// void InitQueue(LinkQueue* q) {
//     q->front=q->rear=NULL;
// }
//
// void Enqueue(LinkQueue* q,TreeNode* x){
//     QueueNode* newNode=(QueueNode*)malloc(sizeof(QueueNode));
//     if(newNode==NULL) {
//         exit(1);
//     }
//     newNode->data=x;
//     newNode->next=NULL;
//
//     if(q->front==NULL&&q->rear==NULL) {
//         q->front=q->rear=newNode;
//     }else {
//         q->rear->next=newNode;
//         q->rear=q->rear->next;
//     }
// }
//
// TreeNode* Dequeue(LinkQueue* q) {
//     if(q->front==NULL) {
//         return NULL;
//     }
//     QueueNode* tmp=q->front;
//     q->front=q->front->next;
//     TreeNode* node=tmp->data;
//     if(q->front==NULL) {
//         q->rear=NULL;//必须要这步
//     }
//     free(tmp);
//     return node;
// }
//
// // 创建新节点
// TreeNode* ChaRuElem(DataType value) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (newNode == NULL) {
//         exit(0);
//     }
//     newNode->value = value;
//     newNode->right = newNode->left = NULL;
//     return newNode;
// }
//
// // 插入节点
// TreeNode* ChaRuNode(TreeNode* root, DataType value) {
//     if (root == NULL) {
//         return ChaRuElem(value);
//     }
//     if (value < root->value) {
//         root->left = ChaRuNode(root->left, value);
//     } else {
//         root->right = ChaRuNode(root->right, value);
//     }
//     return root;
// }
//
// // 从一个数组按层次构造一棵完全二叉树
// TreeNode* BuildCompleteTree(DataType arr[], int n) {
//     if (n == 0) return NULL;
//     // 先为每个元素创建节点
//     TreeNode** nodes = malloc(n * sizeof(TreeNode*));
//     for (int i = 0; i < n; i++) {
//         nodes[i] = malloc(sizeof(TreeNode));
//         nodes[i]->value = arr[i];
//         nodes[i]->left = nodes[i]->right = NULL;
//     }
//     // 再按下标关系连父子
//     for (int i = 0; i < n; i++) {
//         int l = 2*i + 1;
//         int r = 2*i + 2;
//         if (l < n) nodes[i]->left  = nodes[l];
//         if (r < n) nodes[i]->right = nodes[r];
//     }
//     TreeNode* root = nodes[0];
//     free(nodes);
//     return root;
// }
//
// //先序
// void PrePrint(TreeNode* root) {
//     if(root) {
//         printf("%d ",root->value);
//         PrePrint(root->left);
//         PrePrint(root->right);
//     }
// }
//
// //释放内存
// void FreeTree(TreeNode* root) {
//     if(root) {
//         FreeTree(root->left);
//         FreeTree(root->right);
//         free(root);
//     }
// }
//
// bool IsCompleteTree(TreeNode* root) {
//     if(root==NULL) {
//         return true;//空树是完全二叉树
//     }
//     LinkQueue q;
//     InitQueue(&q);
//     Enqueue(&q,root);
//     bool isempaty=false;
//     while (q.front!=NULL) {
//         TreeNode* p=Dequeue(&q);
//         if(p==NULL) {
//             isempaty=true;
//         }else {
//             if(isempaty) {
//                return false;//在入队之前判断是否有空节点
//             }
//             //这部分入队不用判断节点存在，因为需要空节点入队判断完全二叉树
//             Enqueue(&q,p->left);
//             Enqueue(&q,p->right);
//         }
//     }
//     return true;
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     int value[]={40,30,60,10,20,50,70};
//     int length=sizeof(value)/sizeof(value[0]);
//
//     TreeNode* root = BuildCompleteTree(value, length);
//
//     boolean result=IsCompleteTree(root);
//     if(result) {
//         printf("是完全二叉树\n");
//     }else {
//         printf("不是完全二叉树\n");
//     }
//     FreeTree(root);
//     return 0;
// }